/**
 * 给定数组nums，找到一个具有最大和的连续子数组
 * example：[-2,1,-3,4,-1,2,1,-5,4]
 * memo =   [-2,1,-2,4,3,5,6,1,5]
 * return [4,-1,2,1] ==> 6
 * 动态规划
 */
var maxSubArray = function (nums) {
    // 若当前值大则新开一个数组，当前值作为第一个元素
    // 否则就把当前值加入到之前的数组中

    // memo记录每个位置能取得的最大值
    const memo = []
    memo[0] = nums[0]
    let max = nums[0]
    for (let i = 1; i < nums.length; i++) {
        // 检查 当前值nums[i] 是否比 当前值加上之前的数组之和，即nums[i]+memo[i-1] 大
        // 记录二者中更大的
        memo[i] = Math.max(nums[i] + memo[i - 1], nums[i])
        
        // 每生成一个memo[i]就与max比较
        max = Math.max(max, memo[i])
    }

    return max
}